In this paper, we study a class of graph drawings that arise from bobbin lacepatterns. The drawings are periodic and require a combinatorial embedding withspecific properties which we outline and demonstrate can be verified in lineartime. In addition, a lace graph drawing has a topological requirement: itcontains a set of non-contractible directed cycles which must be homotopic to$(1,0)$, that is, when drawn on a torus, each cycle wraps once around the minormeridian axis and zero times around the major longitude axis. We provide analgorithm for finding the two fundamental cycles of a canonical rectangularschema in a supergraph that enforces this topological constraint. The polygonalschema is then used to produce a straight-line drawing of the lace graph insidea rectangular frame. We argue that such a polygonal schema always exists forcombinatorial embeddings satisfying the conditions of bobbin lace patterns, andthat we can therefore create a pattern, given a graph with a fixedcombinatorial embedding of genus one.
展开▼
